package leetcode.周赛.双周赛.第89场;

import leetcode.每日一题.完全平方数;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author ：zsy
 * @date ：Created 2022/10/15 10:49 PM
 * @description：
 */
public class 二的幂数组中查询范围内的乘积 {
    @Test
    public void test() {
        new Solution().productQueries(13 ,new int[][]{});
    }

    class Solution {
        public int[] productQueries(int n, int[][] queries) {
            List<Integer> list = new ArrayList<>();
            int num;
            if (n % 2 == 0) {
                num = n;
            } else {
                num = (n + 1) / 2;
            }
            while (num != 1) {
                list.add(num);
                num /= 2;
            }
            if (n % 2 != 0) {
                list.add(1);
            }
            Collections.reverse(list);
            int[] ans = new int[queries.length];
            int[] powers = new int[list.size() + 1];
            powers[0] = 1;
            for (int i = 1; i < list.size() + 1; i++) {
                powers[i] = list.get(i - 1) * powers[i - 1];
            }
            System.out.println(Arrays.toString(powers));
            for (int i = 0; i < queries.length; i++) {
                int[] query = queries[i];
                ans[i] = powers[query[1] + 1] / powers[query[0]];
            }
            return ans;
        }
    }
}

